Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 10067 - Playing with wheels / 10067.cpp
blob9084efc3a91370ab7e852d5f68ee4e3549eb775e
1 #include <iostream>
2 #include <queue>
3 #include <vector>
4 #include <sstream>
7 using namespace std;
9 inline string intToStr(const int &n){stringstream ss; ss<<n; string s; ss>>s; return s; }
10 inline int strToInt(const string &n){stringstream ss; ss<<n; int s; ss>>s; return s; }
12 int main(){
13 int cases;
14 cin >> cases;
15 while (cases--){
16 vector<bool> forbidden(10000, false);
17 vector<bool> visited(10000, false);
20 int start = 0;
21 for (int i=0; i<4; ++i){
22 int x; scanf("%d", &x);
23 start = (start * 10) + x;
26 int end = 0;
27 for (int i=0; i<4; ++i){
28 int x; scanf("%d", &x);
29 end = (end * 10) + x;
32 int n;
33 cin >> n;
34 while (n--){
35 int f=0;
36 for (int i=0; i<4; ++i){
37 int x; scanf("%d", &x);
38 f = (f * 10) + x;
40 forbidden[f] = true;
43 queue<pair<int, int> > q;
44 int answer = -1;
45 q.push(make_pair(start, 0));
46 while (!q.empty()){
47 int node = q.front().first;
48 int dist = q.front().second;
49 q.pop();
50 if (node == end){
51 answer = dist;
52 break;
54 if (visited[node]){
55 continue;
57 visited[node] = true;
58 for (int i=0; i<4; ++i){
59 stringstream ss;
60 ss << node;
61 string s;
62 ss >> s;
63 string t;
64 char digit;
65 int neighbour;
67 t = s;
68 digit = s[i];
69 digit = '0' + ((digit - '0' + 1) % 10);
70 t[i] = digit;
71 //cout << "t es: " << t << endl;
72 //cout << "neighbour es: " << strToInt(t) << endl;
73 neighbour = strToInt(t);
74 if (!forbidden[neighbour]){
75 q.push(make_pair(neighbour, dist + 1));
76 //cout << "Empuje " << q.front().first << endl;
79 t = s;
80 digit = s[i];
81 digit = '0' + ((digit - '0' + 9) % 10);
82 t[i] = digit;
83 neighbour = strToInt(t);
84 //cout << "neighbour es: " << strToInt(t) << endl;
85 if (!forbidden[neighbour]){
86 q.push(make_pair(neighbour, dist + 1));
87 //cout << "Empuje " << q.front().first << endl;
91 cout << answer << endl;
94 return 0;